package com.leecode.xiehf.page_06;

import com.leecode.Printer;

/**
 * 给你一个整数 n ，请你找出并返回第 n 个 丑数 。
 *
 * 丑数 就是只包含质因数 2、3 和/或 5 的正整数。
 *
 * https://leetcode-cn.com/problems/ugly-number-ii/
 */
public class Solution_0264 extends Printer {

    public static void main(String[] args) {
        Solution_0264 solution = new Solution_0264();
        int number = solution.nthUglyNumber(11);
        System.out.println(number);
    }

    public int nthUglyNumber(int n) {

        int x = 0;
        int y = 0;
        int z = 0;
        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            dp[i] = Math.min(Math.min(2 * dp[x], 3 * dp[y]), 5 * dp[z]);
            if (dp[i] == 2 * dp[x]) {
                x++;
            }
            if (dp[i] == 3 * dp[y]) {
                y++;
            }
            if (dp[i] == 5 * dp[z]) {
                z++;
            }
        }
        return dp[n - 1];
    }
}
